<?php

/*
	Write a function isBST(BinaryTree *node) to verify if a given binary tree is a Binary Search Tree (BST) or not.

	Best example to demonstrate how useful is the state variable during a recursion.
*/

require_once 'util.php';

importJS();

$arr = generateRandomArray(0, 99, 10);

$bst = null;
foreach( $arr as $value ){
	$bst = bst_insert($value, $bst);
}

$bt = null;
foreach( $arr as $value ){
	$bt = bt_insert($value, $bt);
}

bt_draw($bst);
echo "<br/>";
if( isBST($bst) ){
	echo "Is a BST.";	
}
else {
	echo "Is not a BST.";		
}

echo "<br/>";

bt_draw($bt);
echo "<br/>";
if( isBST($bt) ){
	echo "Is a BST.";	
}
else {
	echo "Is not a BST.";		
}

function isBST( $root ){
	if( !$root ){
		return false;
	}
	$min = 0;
	$max = PHP_INT_MAX;
	return isBSTRecursive( $root, $min, $max );
}

function isBSTRecursive( $root, $min, $max ){
	if( $root->value > $max || $root->value < $min ){
		return false;
	}

	$left = $root->left ? isBSTRecursive( $root->left, $min, $root->value ) : true;
	$right = $root->right ? isBSTRecursive( $root->right, $root->value, $max ) : true;

	return $left && $right;
}

